#include<stdio.h>
#include<stdlib.h>
#define	 N 10
void merge(int* r, int left, int mid, int right)
{
	int* tmp = (int*)malloc(sizeof(int) * (right - left + 1));
	int i = left;
	int j = mid+1;
	int k = 0;
	while (i <= mid&&j<=right)
	{
		if (r[i] <= r[j])
		{
			tmp[k++] = r[i++];
		}
		else
		{
			tmp[k++] = r[j++];
		}
	}
	while (i <= mid)
	{
		tmp[k++] = r[i++];
	}
	while (j <= right)
	{
		tmp[k++] = r[j++];
	}
	for (int i = left, k = 0; i <= right; i++, k++)
	{
		r[i] = tmp[k];
	}
}

void MergeSort(int* a, int left, int right)
{
	if (left < right)
	{
		int mid = (left + right)/2;
		MergeSort(a, left, mid);
		MergeSort(a, mid + 1, right);
		merge(a, left, mid, right);
		return;
	}
	else
	{
		return;
	}


}
int main()
{

	int arr[4] = { 4,3,2,1 };
	int se = sizeof(arr) / sizeof(int);
	int right = se - 1;	
	MergeSort(arr, 0, right);
	for (int i = 0; i < 4; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}